1. Field of the Invention
This invention relates to an improvement in the technology for calculating a solution of a so-called constraint-satisfaction problem so that a large problem may be solved speedily.
2. Description of the Related Art
A constraint-satisfaction problem is known as a problem for assigning a set of consistent values to a set of variables. A set of consistent values means that these values satisfy combinational constraints defined of the set of variables. Hereafter, each variable is corresponded to a part of a thing e.g., a system, a product, etc., and each value is corresponded to an alternative to implement the part. Each part may be provided with multiple choices (alternatives) and constraints, such as permissible and impermissible combinations, exist on a combination of alternatives selected respectively for different parts. A solution for the constraint-satisfaction problem is a combination of alternatives that may be applied to all parts so that all constraints are satisfied.
An example of the constraint-satisfaction problem is shown below. Assume that machine X consists of four parts, A, B, C, and D, and that three implementation methods are provided for each of the four parts. That is, implementation methods a1, a2, and a3 (hereafter represented as {a1, a2, a3}) are provided for part A, {b1, b2, b3} for part B, {c1, c2, c3} for part C, and {d1, d2, d3} for part D. Each choice (for example, implementation method a1) for a part is called an alternative.
In addition, assume that there is a constraint that the same implementation number cannot be used between each two parts: that is, between, A and B, A and C, A and D, B and C, B and D, and C and D. For example, if the implementation method of part A is aj (j=1, 2, 3), then the implementation methods of parts B, C, and D must be bk, ck, and dk (kxe2x89xa0j), respectively. Similarly, if the implementation method of part B is bj (j=1, 2, 3), then the implementation methods of parts C and D must be ck and dk (kxe2x89xa0j), respectively. If the implementation method of part C is cj (j=1, 2, 3), then the implementation method of part D must be dk (kxe2x89xa0j).
Under the constraint described above, consider selecting implementation methods A, B, C, and D to design machine X so that all the conditions required for a combination(combination conditions) are satisfied. In this example, since there is not any combination of implementation methods, or any solution, which satisfies all the combination conditions, machine X cannot be designed. However, making of this judgment on the constraint-satisfaction problem requires that all the combinations of the implementation methods for each part are checked, as shown below, to see whether they satisfy the combination conditions:
{a1, b1, c1, d1}
{a1, b1, c1, d2}
{a1, b1, c1, d3}
{a1, b1, c2, d1}
{a1, b1, c2, d2}
As understood from the combinations above, it is difficult for a designer to make such a judgment even if combinations for only four parts are checked as this example. If combinations for a more large number of parts are checked, it becomes more difficult to make such a judgment. For example, if there are as many as 30 parts and four implementation methods are provided for each of the four parts, a huge number of combinations of alternatives must be checked. It is virtually impossible to check each combination as described above. For this reason, a solution for a constraint-satisfaction problem has been found, in most cases, using a trial-and-error method based on experience.
The constraint-satisfaction problem is not limited to a field where an alternative must be selected for each of the parts that make up a machine such as the one described above. The problem may be applied to many other fields too; for example, it may be applied to how parameters should be specified for each part of a software product or how a plurality of objects should be arranged in a limited area. Therefore, the constraint-satisfaction problem occupies a very important position, for example, in building an expert system.
In general, the constraint-satisfaction problem is defined as follows. That is, when a system (problem) includes a plurality of parts each having a finite number of alternatives used for implementation of each part or its function and when there is a constraint on the combination of two alternatives of each pair of parts in said plurality of parts, the constraint-satisfaction problem is a problem that finds an alternative satisfying the constraint for each part.
However, except a special case, the constraint-satisfaction problem is an NP complete problem. Here, let y-th power of x be represented as xe2x80x9cx{circumflex over ( )}yxe2x80x9d. Then, the NP complete problem refers to a problem whose amount of calculation for solving the problem may be represented as described below. That is, let the number of parts be N, and the maximum number of alternatives allowed for each part be d. In this case, finding of a combination of alternatives consistent with all parts may require d{circumflex over ( )}N calculation at the maximum. For example, if N is 100 and the maximum number of alternatives is 2, 2{circumflex over ( )}100 calculations may be necessary at the maximum. It is impossible to carry out such calculations within a time expendable in practical applications.
As a method for solving for the constraint-satisfaction problem, there is a method which reduces the amount of calculation by localizing the range affected by a constraint. (Reference: Rina Dechter, Judea Pearl: xe2x80x9cNetwork-Based Heuristics for Constraint-Satisfaction Problemsxe2x80x9d, Artificial Intelligence 34 (1988)). However, during calculation, this method introduces constraint relations which do not exist at first and therefore requires about d{circumflex over ( )}N calculations in many cases.
A polynomial calculation method is also available for solving a problem where a constraint graph representing a constraint relation between parts is represented as a tree structure or as a K-tree structure which is an extension of a tree structure (Reference: Eugene Freuder, xe2x80x9cComplexity of K-Tree Structured Constraint Satisfaction Problemsxe2x80x9d). However, this method requires conditions that are rarely satisfied in a practical application.
For the reason described above, a conventional method for solving the constraint-satisfaction problem, which is very important in building an expert system, has been capable of handling very small-scaled problems only, except special cases such as when problems are represented as tree-structured graphs representing the constraint relation between parts.
Consequently, it is desired to provide a system and a method which are useful for solving a large constraint-satisfaction problem at a high speed. Also, it is desired to provide a system and a method which are useful for building a machine or a computer program system, including a plurality of parts for each of which a plurality of alternatives are provided when constraints exist on combinations of alternatives for different parts, in such a manner that the constraint is satisfied more easily than the related art.
In an aspect, the present invention is a system for calculating a solution of a constraint-satisfaction problem including a plurality of parts for each of which a plurality of alternatives are provided when a constraint exists on a combination of alternatives selected respectively for different parts in said plurality of parts. The system divides a set of alternatives provided for a plurality of parts of a given problem to be solved into a plurality of subsets such that each subset has not more than two alternatives for each part, and analyzes a combination of alternatives for each subset to check whether the combination of alternatives satisfies said constraint, whereby allowing a solution of the problem to be calculated from the analyzed combination. Calculation of a solution for a subset in which each part has not more than two alternatives, requires a very short period of time even if the problem includes many parts. This means that the sum of the times required for finding solutions for all the subsets, is much shorter than the time required for finding a solution for the original problem as it is. Thus the system is useful for solving a large constraint satisfaction problem at a high speed.
Preferably, the system may calculate a reachable value set representing a combination of sets of alternatives defined on each part satisfying said constraint for each of said plurality of subsets, complete the calculated reachable value set, and calculate a solution from the completed reachable value set. The calculation of a reachable value set can be carried out in a very short time even if the problem includes many parts. Thus the system greatly reduces the time required for calculating a solution of the whole problem.
In another aspect, the present invention is a system for constructing a system including a plurality of parts for each of which a plurality of alternatives are provided when a constraint exists on a combination of alternatives selected respectively for different parts in said plurality of parts. The constructing system divides a set of alternatives provided for a plurality of parts of a given system to be constructed into a plurality of subsets such that each subset has not more than two alternatives for each part, and constructs a system which satisfies said constraint by calculating a combination of alternatives which satisfies said constraint for each of said plurality of subsets. The constructing system is useful for constructing a complicated system which includes many parts when a constraint exists on a combination of alternatives for different parts, more easily than the constructing system according to the related art.
Other and further objects, features, and advantages of the invention will appear more fully from the following description.